package cc.rico.algorithm;

/**
 * @Author: Dell
 * @Date: 2018/12/5
 * @Description:
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] items = new int[] {23, 22, 5, 6, 90, 43, 90, 1};
        PrintUtil.printArray(items);

        int[] results = sort(items);
        PrintUtil.printArray(results);
    }

    public static int[] sort(int[] items) {
        if(items==null || items.length==0) {
            return null;
        }
        if(items.length == 1) {
            return items;
        }

        if(items.length==2) {
            if(items[0] <= items[1]) {
                return items;
            }

            if(items[0] > items[1]) {
                int temp = items[0];
                items[0] = items[1];
                items[1] = temp;
                return items;
            }
        }

        int pivot = items[0];

        int partOneCount = 0;
        int partTwoCount = 0;

        for(int i=1; i<items.length; i++) {
            if(pivot > items[i]) {
                partOneCount++;
            } else {
                partTwoCount++;
            }
        }

        int[] partOne = new int[partOneCount];
        int[] partTwo = new int[partTwoCount];

        int partOneIndex = 0;
        int partTwoIndex = 0;

        for(int i=1; i<items.length; i++) {
            if(pivot > items[i]) {
                partOne[partOneIndex] = items[i];
                partOneIndex++;
            } else {
                partTwo[partTwoIndex] = items[i];
                partTwoIndex++;
            }
        }

        partOne = sort(partOne);
        partTwo = sort(partTwo);

        int[] results = new int[items.length];
        int currentIndex = 0;

        for(int i=0; i<partOneCount; i++) {
            results[currentIndex] = partOne[i];
            currentIndex++;
        }

        results[currentIndex] = pivot;
        currentIndex++;

        for(int i=0; i<partTwoCount; i++) {
            results[currentIndex] = partTwo[i];
            currentIndex++;
        }

        return results;
    }


}
